package com.sicheng.lc.杂题;

import java.util.ArrayList;

/**
 * @author zsc
 * @version 1.0
 * @date 2022/7/9 16:55
 */
public class 凑数字 {
    //https://leetcode-cn.com/problems/longest-repeating-character-replacement/
    //23123
    //[2,4,9]

    public static void main(String[] args) {
        凑数字 s = new 凑数字();
        int[] nums = {2, 4, 9};
        long n = 244788;
        System.out.println(s.getNumber(n, nums));
    }

    public long getNumber(long n, int[] nums) {
        boolean[] cnt = new boolean[10];
        int count = 0;
        for (int num : nums) {
            if (num >= 0 && num <= 9) {
                cnt[num] = true;
                count++;
            }
            if (count == 10)
                break;
        }
        if (count == 1 && cnt[0])
            return 0;
        ArrayList<Integer> bits = new ArrayList<>();
        // 把n的每一位数扣出来存储
        while (n > 0) {
            bits.add((int) (n % 10));
            n /= 10;
        }
        long res = 0;

        boolean max = false;
        // 从高位开始凑
        for (int i = bits.size() - 1; i >= 0; i--) {
            int j = bits.get(i);
            if (max)
                j = 9;
            for (; j >= 0; j--) {
                if (cnt[j]) {
                    res = res * 10 + j;
                    //当前位凑到的数 j < n 的对应位，之后的位从最大的开始凑
                    if (!max && j < bits.get(i))
                        max = true;
                    break;
                }
            }
            if (j < 0)
                return -1;
        }
        return res;
    }
}
